The DevLib Development Library

This Chapter describes the various files in the folder DevLibSrc.  The development library, 
DevLib, provides a set of common functions used by a C compiler, assembler, linker and 
debugger, as well as SPP, SDEL and SDIF.  These routines are not specific to the Macintosh: they 
may be of interest to C programmers using a wide variety of environments.


DevLib defines a set of classes.  Each class is represented by a .h file and one or two .c files.  The 
.c files represent the ÒbaseÓ methods of each class.  When a member (method or data) of a class 
must be over-ridden by an application, that member is not defined in DevLibSrc.  Rather, it is 
defined in an application-specific, say XXyy.c file.  That is, XX stands for the name of your 
application, while yy stands for the particular class.


The externally visible public members (functions and data) of any class are exactly those functions 
and data declared in the .h file for the class.  In particular, each .h file contains a function prototype 
for each public method.


The library consists of the following classes and auxiliary headers.  Classes are identified by the 
name of its .c file.  The .c file typically contains more complete documentation than the 
corresponding .h file.


The LIBmem class is particularly interesting.  It describes an optimal method of allocating memory 
based on so-called lifetime classes.  Also, the LIBobj class describes replacements for malloc and 
free.  These classes complement each other; lifetime classes ultimately call malloc to get blocks of 
memory.



LIBcmnd.c

This class parses a disk parameter file into a set of argv arguments.  I use parameter files 
containing hundreds of Sherlock arguments.  Not only do the arguments control the program, they 
provide a record of what I am working on.


The init_args function is most important routine of this class.  init_args reads a text file, parses it 
into separate arguments, allocates an argv vector, fills in the argv vector with pointers to the 
arguments, and computes the value of argc.

LIBcvt.c

This class converts various kinds of variables into strings; it is a type-safe replacement for sprintf.  
This class guards against overwriting the sprintf buffer.  Most routines in this class require the 
caller to supply a buffer into which the resulting string is put.  The routines checks that the string 
does not overflow the buffer.  These checks are not foolproof because they rely on the stated size 
of the buffer passed by the caller


This class is used mainly by the stream output routines in LIBes.c.  Once in a while, however, 
these routines are useful in their own right.


The compile-time constant CVT_USE_SPRINTF allows this file to avoid all calls to sprintf.  This 
was useful when bootstrapping a C compiler.



LIBend.c and XXend.c

This class handles end-of-program processing.  Each application must define its own 
end_close_all method, in an application-specific file, XXend.c.



LIBenv.c

This class reports on various system-dependent quantities, such as heap statistics that may be kept 
by the operating system itself.  At present, the code reports on the status of Macintosh heap zones.  
This class is not defined for Power Macs.



The files LIBes.c and XXes.c

This class contains many stream output routines that are type safe replacements for fprintf.  SPP, 
SDEL and SDIFÊcontain many examples of how to use these routines.


All output from these routines eventually passes through the es routine, which is not defined in 
LIBes.  Instead, each application is supposed to ÒoverrideÓ es by providing its own version of es, 
in an application-specific file, XXes.c. On the Macintosh es calls log_sout in LIBlog.c; on other 
machines es could call fprintf(stderr, Ò%sÓ, s);

Each application must also provide definitions for the following routines:  ecnl, ecnls, ecblanks, 
es_assert_failed and es_internal_err.  See the file SPPes.c for an example of the per-application 
definitions of these routines.


The ecnl routine deserves special mention.  It outputs a conditional newline.  That is, it outputs a 
newline only if the last character output was not a newline.  Conditional newlines make it easy to 
generate correct spacing without requiring strict coding conventions.


Short function names are very important here.  In particular, es, enl, ecnl and eint must have short 
names to be convenient to use.  In effect, these names are all variants of the C++   <<   operator.



LIBio.c

This class provides slightly enhanced open, close, read and write routines.  This file was more 
useful before the ANSI Standard defined the library rigorously, but it is still sometimes useful to 
isolate system dependencies.



LIBlib.c

This file is not a class.  Rather, it specifies application-specific information to the library.  Make a 
separate copy of this file with a separate name, say XXlib.c,  for each application.  Do not use 
LIBlib.c.  It is only a template.


This is a simple, yet crucial file.  Using variables to contain constant information is an Aha that 
makes it possible for different programs to share the same source code.  In effect, the linker injects 
these constants into the source code of the library.



LIBlist.h

This class consists only of macros;  there is no corresponding .c file.  This file contains type-safe 
macros for list processing.  Using functions instead of macros would require type-defeating casts 
to void *.  Macros can avoid such casts.  Think of these macros as a kind of C++ template. 


Lifetime memory allocation reduces the need for these macros.  (See LIBmem.h for a discussion 
of lifetime allocation.)  Elements of lists almost always have the same lifetime, so it is seldom 
necessary to free list elements explicitly.  With lifetime allocation, the list head is freed at the same 
time all the nodes are freed.  Most list processing simply disappears!

LIBlog.c

This class handles output to a log file and window.  Usually all output from es is directed here.  
Distinguishing this class from the class that prints the error stream simplified the code greatly.


By convention, Sherlock opens a log file when it sees a Sherlock argument of the form


	++>>file_name.


Only one log file can be open at a time.



LIBmem.c, LIBmem.h, XXmem.c and XXmem.h

This class implement what I call the lifetime method of storage allocation.  I have used this method 
of storage allocation in an ANSIÊC compiler that I recently completed.  It is not used in SPP, SDIF 
or SDEL.  I describe it here because it is an important part of DevLib.


Defining lifetimes

Let us define the lifetime of a heap object to be the time (point in the code) at which the object is 
freed.  This definition is deceptively simple.  Note the following:


¥ The lifetime of an object does not depend on when the object is created, only when it is freed.

¥ The type of an object does not influence its lifetime.  Objects of different types and sizes may 
have the same lifetime.

¥ The lifetime of an object is determined when the object is created.  It does not change.


Implementing lifetimes

Arbitrarily many lifetimes may exist in a program.   A global variable points at the head of the list 
of lifetimes.  Position within this list has no significance.  A dynamically allocated node describes 
each lifetime.  Each node contains the following information:


¥ The name of the lifetime.  This name is used to create column headers in dumps of statistics.

¥ A pointer to the head of a list of blocks comprising the memory used by the lifetime.  The first 
block on the list is the current block.  Memory is always allocated from the current block.  A new 
block is added to the list whenever the current block does not contain enough free memory to 
handle a request for more memory.

¥ The number of free bytes in the current block and a pointer to the first free byte.

¥ A pointer to the head of a list of per-type statistics nodes for this lifetime.  Each statistic node 
describes the statistics for objects of the same type in this particular lifetime.  Statistics nodes 
contain statistics and a type name used in dumps.

¥ A pointer to the next lifetime on the global list of all lifetimes.


Allocating memory

I allocate memory use a variety of macros.  The file LIBmem.h contains the basic macros.  The 
new_macro allocates enough bytes to hold an object whose pointer is given.  For example:


	my_type * p;

	new_macro(p, perm_life, perm_type_stat);


perm_life is a pointer to a lifetime node and perm_type_stat a pointer to a statistics node attached to 
perm_life.


For safety, I would define an abbreviation macro defined in an application-defined header, say 
XXmem.h.  A typical abbreviation macro would be:


	#define new_perm_my_type_macro(p) \

		new_macro(p, perm_life, perm_my_type_stat)


This macro ensures that the proper statistic node is used with the proper lifetime. In other words, 
abbreviation macros represent associations, in this example the association of perm_my_type_stats 
with perm_life.


The new_macro is defined as follows in LIBmem.h:


	#define new_macro(p, life, stat) \

		new_size_macro(p, sizeof(*p), life, stat);


new_macro computes the number of bytes to be allocated using sizeof(*p).  This will work 
regardless of what p points to.  The compiler will complain if p is not, in fact, a pointer.  This 
macro is type safe and bullet-proof.



All the real work is done by the new_size macro.  The actual definition of this macro is a bit 
complicated:  see LIBmem.h.  A simplified form of the macro is as follows:


	#define new_size_macro(p, size, life, stat)			\

		// update statistics for stat					\

		if (size > life -> mem_avail) {				\

			p = mem_new_block(size_, life);			\

		}									\

		else {								\

			p = life -> mem_ptr;					\

			life -> mem_ptr   = life -> mem_ptr + size;	\

			life -> mem_avail -= size_;				\

		}									\

	}


Usually, the current block will contain more than size bytes.  In that case, we execute the 
following instructions:


	p = life -> mem_ptr;

	life -> mem_ptr    = life -> mem_ptr + size;

	life -> mem_avail -= size;


Clearly, it's not possible to allocate memory more quickly than these 3 instructions..


When the current block does not contain enough free memory for the requested item, the macro 
call mem_new_block to get a new block of memory.  mem_new_block is defined in LIBmem.c.  
It sets life -> mem_ptr and life -> mem_avail to describe the newly allocated block.  
mem_new_block will usually allocate a standard-sized block (like 1024 bytes), but can allocate an 
arbitrarily large block if the requested number of bytes would not fit in a standard-sized block.


new_size_macro is the fastest possible way to allocate memory.  Indeed, it doesn't matter how fast 
mem_new_block is!  The reason is simple: the current block will usually be big enough to contain 
the next item, assuming that most allocated items are small compared to the standard block size.  
We can arbitrarily decrease the cost of calling mem_new_block by increasing the size of the 
standard block.


So much for allocating memory.  Deallocating memory is even more efficient.  As a consequence 
of the definition of a lifetime, all items with the same lifetime are deallocated at once.  Deallocating 
a lifetime is trivial: we simply free all of the blocks of the lifetime.



LIBobj.c and LIBobj.h

This class provides more robust versions of calloc and free.  This class has a long history: the 
present version if much easier to use and more powerful than previous versions.  This class is 
probably more powerful than some of the malloc replacements being sold today.


Access this class using the obj_new_macro or obj_free_macro, defined in LIBobj.h.  A third 
macro, obj_new_var_tag_macro is much less often used, though it is sometimes essential.


The compile-time constant PRODUCTION controls these macros.  When PRODUCTION is 
#defined, the macros expand essentially to calloc and free.  Otherwise, the macros expand to 
routines that provide memory protection and statistics gathering capabilities.


These routines use a string as a type name without sacrificing efficiency.  I call this the Sherlock 
trick.  How does this work?  LetÕs look at the definition of the debugging version of 
obj_new_macro:


	#define obj_new_macro(the_mem, size, tag) {		\

		static type_des * tp_ = NULL;				\

		the_mem = obj_new_db(size, tag, &tp_);		\

	}


The first time a particular instance of this macro is called, the static variable tp_ is NULL, so 
obj_new_db searches a hashed list of all types it knows about for the tag.  If it is found, it sets tp_ 
to point to the type_des describing the type.  Otherwise it creates a type_des describing the new 
type and points tp_ to it.  The second time a particular instance of this macro is called, tp_ has 
already been set, and obj_new_db can access the type_des directly without any searching at all.


Notice: it is never necessary to initialize a type_des;  obj_new_macro does it automatically.  The 
tag string is enough to initialize the new type.  In effect, the tag is a type.  So to create a new type, 
just call obj_new_macro with a new string argument.  The list of tag names is searched only once 
per instance of the macro, so the time overhead is not noticeable.


Usually the tag argument is a normal, statically allocated string.  The Sherlock trick wonÕt work if 
the tag argument is a variable because tp_ must then be recalculated on each call.  In those rare 
cases, use obj_new_var_tag_macro.  This macro essentially sets tp_ every time it is called.


This class can produce a formatted report of statistics for all objects, similar to the report provided 
by the LIBmem class.  LIBmem allocates memory in blocks, so only those blocks will show up in 
the report created by LIBobj.  


When PRODUCTION is not defined, all memory is preceded and followed by fill bytes that are 
filled with a known pattern.   Most memory overwrites can easily be found by checking these fill 
bytes.


When the ++obj_v Sherlock trace is enabled all fill bytes are checked any time a new object is 
allocated or freed.  Obviously, this takes a lot of time, and it is very useful in finding memory 
problems.


When the ++obj_watch Sherlock trace is enabled all fill bytes are put on a Sherlock watch list.  
(IÕll discuss watch lists below).  This watch list is checked whenever a Sherlock macro is 
executed, so all fill bytes are checked whenever a Sherlock macro is executed.  This option takes 
even more time than the ++obj_v option, but finds memory problems quickly.


Regardless of the settings of ++obj_watch and ++obj_v, the fill bytes of an object are checked 
when it is freed.



LIBos.c

This class provides an output stream.  There are two kinds of routines in this class.  The out_bytes 
routine provides non-text output.  All other routines provide text output.  All text output is 
funneled through the os routine, so redirecting output is feasible and simple.



Sherlock (sl_xxx.c and sl.h)

Sherlock is a way of enabling and disabling code at run time.  Sherlock consists of a large set of 
macros such as TRACE.  TRACE(a,b) executes the code b if the string a has been enabled from 
the command line.  For example,

	

	TRACE("obj_v", obj_check_all());


This macro executes obj_check_all if ++obj_v has been selected on the command line.  If the 
compile-time constant called SHERLOCK is not #defined, all Sherlock macros expand to do-
nothing code.

The second parameter  to the TRACE macro can be any sequence of C source statements.  The 
following is perfectly valid:


	TRACE("xyz",

		{

			int i;

			for(i = 0; i < limit; i++)

				fprintf(stderr, "array[%d]=%d\n", i, array[i]);

		}

	);


In particular, the commas in the call to fprintf do not delimit macro parameters because they are 
inside parentheses.  About the only thing you can't put inside a Sherlock macro is an initializer 
containing commas.


The Sherlock trick is important here.  Without it, we would have to declare and initialize a variable 
for every different tag, xyz in the example above.  This would be intolerable.  The Sherlock trick 
allows us to dispense with tracing variables!  My programs have hundreds of tags that can be 
enabled or disabled independently.  None of these tags require any initialization on my part.  The 
only initialization is a single call to parse the Sherlock arguments and remove them from the argv 
list so they donÕt interfere with the programÕs usual arguments.


My preferred style of using Sherlock has changed a bit since Sherlock was first released:

¥ I no longer use the RETURN_xxx family of macros.  These turned out to be too clumsy.  A 
typical contains a single exit point, immediately preceded by a STATX or TRACEPX macro.  I 
prefer to use goto done to indicate a return from a function.  This complicates some functions, but 
not much.

¥ I often use STATB as the first Sherlock macro.  That way, the timing statistics of the routines are 
not influenced by the tracing that would be produced by TRACEPB.


Watch lists are new.  The SL_WATCH macro places a node describing an area of memory and its 
contents on a list.  This list is checked whenever a Sherlock macro is executed.  I place Sherlock 
macros at the start and end of almost all my functions, so this watch list is examined at the start 
and end of each function.  We can catch memory being trashed within the function that trashed it, 
yet the overhead of examining the watch list is much less than if it were examined after every 
instruction.  By the way, only a few dozen lines of code in sl_macro.c are needed to implement 
watch lists.

LIBtypes.h

This file contains the typedefs for types that are shared among the files of DevLib.  The actual 
definitions of the structs need not appear in this header file!   This has the following advantages:


¥ It allows struct A in a header file H to refer to struct B even though the definition of struct B does 
not appear in H.

¥ Include files can be included in any order because all necessary typedefs are in LIBtypes.h.

¥ Typedefs change rarely, and LIBtypes.h needs change only if a new global type is created.

¥ Include files can correspond closely to C++ classes.  That is, the declarations of derived classes 
need not be contained in the header that contains the declaration of the base class.  Header files can 
describe a single class, whether or not that class is derived from another class.


There are a few drawbacks to using LIBtypes.h, none of which are significant for small and 
medium sized programs.


¥ The typedefs in LIBtypes.h are global, even though they may be used only in one or two files.

¥ All library files depend on LIBtypes.h, so they are a bit less self contained.



Possible Improvements

I keep finding new uses for the Sherlock trick.  One possibility would be to create stat nodes 
automatically by defining the macro MEM_UPDATE_STATS in LIBmem.h as follows:

		

	{								\

		static mem_stat_node * h = NULL;		\

		if (h == NULL) h = mem_init_stats(tag);	\

		// update h as usual				\

	}

		

This would eliminate the need to define and initialize statistics variable.   In particular, you 
wouldnÕt need to change the application-specific version of LIBmem.h to create a new kind of 
node.  Very convenient.


This is a bit slower than the old scheme.  Ignoring (as we should) the time to execute 
mem_init_stats once, the test (h== NULL) almost doubles the time to execute the macro.  
However, statistics are not typically kept in production code, so the speed penalty is usually 
negligible.